#include "BinaryTree.hpp"
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <stack>
#include <queue>

int binaryTreeSize(BinaryTreeNode *root)
{
    if (root == nullptr)
    {
        return 0;
    }
    int size = 1;
    if (root->left != nullptr)
    {
        size += binaryTreeSize(root->left);
    }
    if (root->right != nullptr)
    {
        size += binaryTreeSize(root->right);
    }
    return size;
}

BinaryTreeNode *insertNode(BinaryTreeNode *root, const char *data)
{
    BinaryTreeNode *newNode = (BinaryTreeNode *)malloc(sizeof(BinaryTreeNode));
    newNode->data = data;
    newNode->left = nullptr;
    newNode->right = nullptr;
    newNode->parent = nullptr;
    newNode->root = nullptr;
    if (root == nullptr)
    {
        return newNode;
    }
    newNode->root = root;
    for (BinaryTreeNode *x = root;;)
    {
        if (strcmp(x->data, data) < 0)
        {
            if (x->right == nullptr)
            {
                x->right = newNode;
                x->right->parent = x;
                break;
            }
            x = x->right;
        }
        else
        {
            if (x->left == nullptr)
            {
                x->left = newNode;
                x->left->parent = x;
                break;
            }
            x = x->left;
        }
    }
    return newNode;
}

void PreOrder(BinaryTreeNode *root)
{
    if (root != nullptr)
    {

        std::cout << "Node(" << root->data << ")" << std::endl;
        PreOrder(root->left);
        PreOrder(root->right);
    }
}

void PreOrderNonRecursive(BinaryTreeNode *root)
{
    if (root == nullptr)
    {
        return;
    }
    std::stack<BinaryTreeNode *> nodeStack;
    while (true)
    {
        while (root != nullptr)
        {
            std::cout << "Node(" << root->data << ")" << std::endl;
            nodeStack.push(root);
            root = root->left;
        }
        if (nodeStack.empty())
        {
            break;
        }
        root = nodeStack.top();
        nodeStack.pop();
        root = root->right;
    }
}

void InOrder(BinaryTreeNode *root)
{
    if (root != nullptr)
    {
        InOrder(root->left);
        std::cout << "Node(" << root->data << ")" << std::endl;
        InOrder(root->right);
    }
}

void PostOrder(BinaryTreeNode *root)
{
    if (root != nullptr)
    {
        PostOrder(root->left);
        PostOrder(root->right);
        std::cout << "Node(" << root->data << ")" << std::endl;
    }
}

int binaryTreeHeight(BinaryTreeNode *root)
{

    int rh = 0;
    int lh = 0;
    if (root->left != nullptr)
    {
        lh = 1 + binaryTreeHeight(root->left);
    }
    if (root->right != nullptr)
    {
        rh = 1 + binaryTreeHeight(root->right);
    }
    return rh > lh ? rh : lh;
}

void LevelOrder(BinaryTreeNode *root)
{
    std::queue<BinaryTreeNode *> queue;
    queue.push(root);
    while (!queue.empty())
    {
        root = queue.front();
        queue.pop();
        std::cout << "Node(" << root->data << ")" << std::endl;
        if (root->left != nullptr)
            queue.push(root->left);
        if (root->left != nullptr)
            queue.push(root->right);
    }
}

int IsIsomorphic(BinaryTreeNode *root1, BinaryTreeNode *root2)
{
    if (root1 == nullptr && root2 == nullptr)
    {
        return 1;
    }
    if ((root1 == nullptr && root2 != nullptr) || (root1 != nullptr && root2 == nullptr))
    {
        return 0;
    }
    return IsIsomorphic(root1->left, root2->right) && IsIsomorphic(root1->right, root2->right);
}